package cn.nicklemay.interview.algorithm;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class SearchinRotatedSortedArray_33
{
    /**
     * NOTE : Arrays.binarySearch() 是左闭右开的
     * 1.初始从0开始两个指针lo, high,lo表示递增子序列的开始，high表示结尾的下一个
     *      如：4,5,6,1,2,3的第一个递增子序列lo=0,high=3,第二个递增子序列为lo=3,high=6
     * 2.遍历nums,当nums[i] < nums[i-1]，则找到一个递减的点
     * 3.则lo—>high-1之间是递增子序列
     * 4.当找到下一个递增子序列时，使得lo=high,
     */
    public int search(int[] nums, int target)
    {
        int lo = 0;
        int high = 0;
        if (nums.length != 0)
        {
            if (nums.length == 1)
            {
                return nums[0] == target ? 0 : -1;
            }
            for (int i = 1; i < nums.length; i++)
            {
                if (nums[i - 1] > nums[i])
                {
                    lo = high;
                    high = i;
                    if (nums[lo] <= target && nums[i - 1] >= target)
                    {
                        int res = Arrays.binarySearch(nums, lo, high, target);
                        if (res > -1)
                        {
                            return res;
                        }
                    }
                }
            }
            if (high < nums.length)
            {
                int last = Arrays.binarySearch(nums, high, nums.length, target);
                return last > -1 ? last : -1;
            }
        }
        return -1;
    }

    public static void main(String[] args) throws IOException
    {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        String line;
        while ((line = in.readLine()) != null)
        {
            int[] nums = IOUtil.stringToIntegerArray(line);
            line = in.readLine();
            int target = Integer.parseInt(line);

            int ret = new SearchinRotatedSortedArray_33().search(nums, target);

            String out = String.valueOf(ret);

            System.out.print(out);
        }
    }
}
